import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.concurrent.ThreadLocalRandom;

public class SelfSevenSort {



    public static void swap(int[] arr,int i,int j){
        int tmp=arr[i];
        arr[i]=arr[j];
        arr[j]=tmp;
    }
    /**
     * 二路快排
     * @param
     */
    public static void quickSort2(int[] arr){
        quickSortInternal2(arr,0,arr.length-1);
    }
    // 对 arr[l,r]进行快速排序
    private static void quickSortInternal2(int[] arr, int l, int r) {
        // 分区
        if (l>r) {
            return;
        }
        // arr[l,r]上求分区点，arr[l,p]都小于v,arr[p,r]都大于V
        int p=partition(arr,l,r);
        // 重复上述过程
        quickSortInternal2(arr,l,p-1);
        quickSortInternal2(arr,p+1,r);

    }
    private static int partition(int[] arr, int left, int right){
        int pivot = left;
        int index = pivot+1;
        for (int i = index; i <= right; i++) {
            if(arr[i]<arr[pivot]){
                swap(arr,i,index++);
            }
        }
        swap(arr,pivot,index-1);
        return index-1;
    }
    // 二路快排的分区
    // 返回arr[l,r]上的分区点
    private static int partition2(int[] arr, int l, int r) {
        int v=arr[l];
        // arr[l + 1..i) <= v
        // [l + 1..l + 1) = 0
        int i=l+1;
        // arr(j..r] >= v
        // (r...r] = 0
        int j=r;
        while(true){
            // i从前向后扫描，碰到第一个 >= v的元素停止
            while(i<=j && arr[i]<v){
                i++;
            }
            // j从后向前扫描，碰到第一个 <= v的元素停止
            while(i<=j && arr[j]>v){
                j--;
            }
            if(i>=j){
                break;
            }
            swap(arr,i,j);
            i++;
            j--;
            return j;
        }
        // j落在最后一个 <= v的元素身上
        swap(arr,l,j);
        return j;
    }
    public static void main(String[] args) {
        int[] arr2={9,1,5,8,3,7,4,6,2};
        quickSort2(arr2);
        System.out.println(Arrays.toString(arr2));
    }
}